


#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 
class Solution
{
public:
    void reorderList(ListNode* head)
    {
        if (!head->next || !head->next->next)
            return;

        ListNode* prev = nullptr;
        ListNode* fast = head, * slow = head;

        while (fast && fast->next)
        {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        prev->next = nullptr;

        ListNode* guard1 = new ListNode(0);
        while (slow)
        {
            ListNode* pnext = slow->next;
            slow->next = guard1->next;
            guard1->next = slow;
            slow = pnext;
        }

        ListNode* cur1 = head, * cur2 = guard1->next;
        ListNode* guard2 = new ListNode(0), * tail = guard2;

        while (cur1 && cur2)
        {
            tail->next = cur1;
            tail = cur1;
            cur1 = cur1->next;

            tail->next = cur2;
            tail = cur2;
            cur2 = cur2->next;
        }
        if (cur2)
            tail->next = cur2;

        delete guard1;
        delete guard2;
    }

    ListNode* mergeKLists1(vector<ListNode*>& lists)
    {
        int n = lists.size();

        if (0 == n)
            return nullptr;
        if (1 == n)
            return lists[0];

        ListNode* guard = new ListNode();
        ListNode* tail = guard;

        while (1)
        {
            int flag = 1;
            int mini = INT_MAX;

            for (int i = 0; i < n; ++i)
            {
                if (lists[i])
                {
                    mini = min(lists[i]->val, mini);
                    flag = 0;
                }
            }
            if (flag)
                break;

            tail->next = new ListNode(mini);
            tail = tail->next;

            for (int j = 0; j < n; ++j)
            {
                if (lists[j] && lists[j]->val == mini)
                {
                    lists[j] = lists[j]->next;
                    break;
                }
            }
        }

        tail = guard->next;
        delete guard;

        return tail;
    }

    ListNode* mergeKLists2(vector<ListNode*>& lists)
    {
        int n = lists.size();

        if (0 == n)
            return nullptr;
        if (1 == n)
            return lists[0];

        ListNode* guard = new ListNode();
        ListNode* tail = guard;
        priority_queue<ListNode*, vector<ListNode*>, comp> hp;

        for (const auto& e : lists)
        {
            if (e)
                hp.push(e);
        }

        while (!hp.empty())
        {
            ListNode* top = hp.top();

            tail->next = new ListNode(top->val);
            tail = tail->next;
            hp.pop();

            if (top->next)
                hp.push(top->next);
        }
        tail = guard->next;
        delete guard;

        return tail;
    }

    ListNode* mergeKLists3(vector<ListNode*>& lists)
    {
        int n = lists.size();

        if (0 == n)
            return nullptr;
        if (1 == n)
            return lists[0];

        return _merge(lists, 0, n - 1);
    }

    ListNode* reverseKGroup(ListNode* head, int k)
    {
        if (!head->next)
            return head;
        if (1 == k)
            return head;

        int cnt = 0;
        ListNode* cur = head;

        while (cur)
        {
            ++cnt;
            cur = cur->next;
        }
        cnt /= k;

        cur = head;
        ListNode* guard = new ListNode(-1);
        ListNode* newhead = guard;

        for (int i = 0; i < cnt; ++i)
        {
            ListNode* tmp = cur;
            for (int j = 0; j < k; ++j)
            {
                ListNode* pnext = cur->next;

                cur->next = newhead->next;
                newhead->next = cur;
                cur = pnext;
            }
            newhead = tmp;
        }
        if (cur)
            newhead->next = cur;

        newhead = guard->next;
        delete guard;

        return newhead;
    }

    ListNode* swapPairs1(ListNode* head)
    {
        if (!head || !head->next)
            return head;

        ListNode* cur = head;
        ListNode* guard = new ListNode(-1), * newhead = guard;

        while (cur && cur->next)
        {
            ListNode* tmp = cur;
            for (int i = 0; i < 2; ++i)
            {
                ListNode* pnext = cur->next;

                cur->next = newhead->next;
                newhead->next = cur;
                cur = pnext;
            }
            newhead = tmp;
        }
        if (cur)
            newhead->next = cur;

        newhead = guard->next;
        delete guard;

        return newhead;
    }

private:
    ListNode* _merge(vector<ListNode*>& li, int lf, int rg)
    {
        if (lf > rg)
            return nullptr;
        if (lf == rg)
            return li[lf];

        ListNode newnode;
        ListNode* guard = &newnode;
        ListNode* tail = guard;
        int mid = lf + ((rg - lf) >> 1);

        ListNode* cur1 = _merge(li, lf, mid);
        ListNode* cur2 = _merge(li, mid + 1, rg);

        if (!cur1)
            return cur2;
        if (!cur2)
            return cur1;

        while (cur1 && cur2)
        {
            if (cur1->val <= cur2->val)
            {
                tail->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail->next = cur2;
                cur2 = cur2->next;
            }
            tail = tail->next;
        }
        if (cur1)
            tail->next = cur1;
        if (cur2)
            tail->next = cur2;

        return guard->next;
    }

    struct comp
    {
        bool operator()(const ListNode* x, const ListNode* y)
        {
            return x->val > y->val;
        }
    };
};

std::string solution1(std::string dna_sequence)
{
    int n = dna_sequence.size();
    dna_sequence += dna_sequence;
    string ans = dna_sequence;

    for (int i = 0; i < n; ++i)
    {
        string cur = dna_sequence.substr(i, n);
        if (cur < ans)
            ans = cur;
    }

    return ans;
}

std::string solution2(const std::string& s)
{
    string ans;
    int n = s.size();
    int beg = 0, pointPos = 0;

    for (int i = 0, flag = 1; i < n; ++i)
    {
        if (flag && '0' != s[i])
        {
            beg = i;
            flag = 0;
        }
        if ('.' == s[i])
        {
            pointPos = i;
            break;
        }
    }
    if (0 == pointPos)
        pointPos = n;

    int div = (pointPos - beg) % 3;
    if (div)
    {
        ans += s.substr(beg, div);
        if (n > 3)
            ans += ",";
    }
    beg += div;

    for (int i = beg; i < pointPos; i += 3)
    {
        ans += s.substr(i, 3);
        if (i + 3 != pointPos)
            ans += ",";
    }
    ans += s.substr(pointPos);

    return ans;
}

int main() {
    std::cout << (solution2("1294512.12412") == "1,294,512.12412") << std::endl;
    std::cout << (solution2("0000123456789.99") == "123,456,789.99") << std::endl;
    std::cout << (solution2("987654321") == "987,654,321") << std::endl;
    std::cout << (solution2("33") == "33") << std::endl;
}